package fun.ticsmyc.question.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 241. 为运算表达式设计优先级
 */
public class 记忆化搜索区间dp {


    static final int ADD = -1;
    static final int SUB = -2;
    static final int MULTI = -3;

    public List<Integer> diffWaysToCompute(String expression) {
        // 数字 ，操作， 数字 ， 操作，数字，操作
        List<Integer> ops = new ArrayList<Integer>();
        for (int i = 0; i < expression.length(); ) {
            if (!Character.isDigit(expression.charAt(i))) {
                if (expression.charAt(i) == '+') {
                    ops.add(ADD);
                } else if (expression.charAt(i) == '-') {
                    ops.add(SUB);
                } else {
                    ops.add(MULTI);
                }
                i++;
            } else {
                int cur = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    cur = cur * 10 + (expression.charAt(i) - '0');
                    i++;
                }
                ops.add(cur);
            }
        }

        List<Integer>[][] dp = new List[ops.size()][ops.size()];
        for (int i1 = 0; i1 < dp.length; i1++) {
            for (int i2 = 0; i2 < dp[i1].length; i2++) {
                dp[i1][i2] = new ArrayList<>();
            }
        }
        return dfs(dp, 0, ops.size() - 1, ops);

    }

    private List<Integer> dfs(List<Integer>[][] dp, int l, int r, List<Integer> ops) {
        if (dp[l][r].isEmpty()) {
            if (l == r) {
                //只有一个数字， 不用计算 直接加
                dp[l][r].add(ops.get(l));
            } else {
                //从i+1位置的操作符分割，分别计算两边
                for (int i = l; i < r; i += 2) {
                    List<Integer> left = dfs(dp, l, i, ops);
                    List<Integer> right = dfs(dp, i + 2, r, ops);
                    for (Integer lv : left) {
                        for (Integer rv : right) {
                            if (ops.get(i + 1) == ADD) {
                                dp[l][r].add(lv + rv);
                            } else if (ops.get(i + 1) == SUB) {
                                dp[l][r].add(lv - rv);
                            } else {
                                dp[l][r].add(lv * rv);
                            }
                        }
                    }

                }
            }
        }
        return dp[l][r];
    }


}
